/*
      该种实现适用于有序数组且重复的指定找最左边的那个，查找一个值等于给定值的元素
      思想：
        1. 先找到第一个等于给定值的元素
        2. 然后向右遍历，直到找到最后一个等于给定值的元素
      时间复杂度：O(logn)
      空间复杂度：O(1)
 */


package com.diudiu.BinarySearch;

public class BinarySearchRightMost02 {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 6, 7, 9, 9, 9, 9, 9, 11, 24, 56, 66, 77, 88, 99, 121, 234, 345};
        int target = 346;
        int result = myBinarySearchRightMost02(array, target);
        System.out.println(result);
    }

    private static int myBinarySearchRightMost02(int[] array, int target) {
        //计算数组长度
        int len = array.length - 1;
        //左边指针
        int left = 0;
        //右边指针
        int right = len;
        while (left <= right) {
            //中间变量
            //注：>>>无符号右移，忽略符号位，空位都以0补齐，避免用 / 造成失误
            int mid = (left + right) >>> 1;
            //目标值小于中间值
            if (target < array[mid]) {
                //右指针赋值为中间值减一
                right = mid - 1;
            } else {
                //左指针赋值为中间值加一
                left = mid + 1;
            }
        }
        //找到就返回该元素索引，找不到就返回目标元素插入点
        return right;
    }

}

